import random
# Pomocne funkcije
def mod_pow(a, n, m):
result = 1
a = a % m
while n > 0:
if n % 2 == 1:
result = (result * a) % m
a = (a * a) % m
n = n // 2
return result
def miller_rabin(n, k):
if n <= 3:
if n == 1:
return False
return True
# n prost => n neparan => n = (2 ^ r) * d + 1
d = n - 1
r = 0
while d % 2 == 0:
r = r + 1
d = d // 2
for i in range(k):
a = random.randrange(2, n - 1)
x = mod_pow(a, d, n)
if x == 1 or x == n - 1:
continue
wittness = True
for j in range(r - 1):
x = mod_pow(x, 2, n)
if x == 1:
return False
if x == n - 1: # n - 1 = -1 (mod n)
wittness = False
break
if wittness:
return False
return True
def get_prime(limit, k = 20):
is_prime = False
while not is_prime:
n = random.randrange(limit)
is_prime = miller_rabin(n, k)
return n
# Pomoćna funkcija, prošireni Euklidov algoritam
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
# Pomoćna funkcija, prošireni Euklidov algoritam
def ext_gcd(a, b):
if b == 0:
return (a, 1, 0)
g, x, y = ext_gcd(b, a % b)
return (g, y, x - a // b * y)
def mod_inv(a, m):
g, x, y = ext_gcd(a, m)
if g != 1:
print("Vrednosti a i m nisu uzajamno proste!")
else:
return x % m
class ElGamal:
def __init__(self, n, g):
self.g = g
self.n = n
self.priv = random.randrange(2, n)
self.pub = pow(g, self.priv, n)
def encrypt(self, m, pub_B):
k = random.randrange(2, self.n)
mask = pow(self.g, k, self.n)
E = pow(pub_B, k, self.n)
me = (m * E) % self.n
return (me, mask)
def decrypt(self, me, mask):
E = pow(mask, self.priv, self.n)
E_inv = mod_inv(E, self.n)
m = (me * E_inv) % self.n
return m
n = get_prime(2**256)
g = random.randrange(2, n)
Aeg = ElGamal(n, g)
Beg = ElGamal(n, g)
print(f'A ---[PubA: {Aeg.pub}]--> B')
print(f'A <--[PubB: {Beg.pub}]--- B')
print()
m1 = 123000
(me1, mask_k1) = Aeg.encrypt(m1, Beg.pub)
print(f'M1: {m1}')
print(f'A --[M1e: {me1}, mask_k1: {mask_k1}]--> B')
md1 = Beg.decrypt(me1, mask_k1)
print(f'B receives: {md1}')
print()
m2 = 45600
(me2, mask_k2) = Beg.encrypt(m2, Aeg.pub)
print(f'M2: {m2}')
print(f'A <--[M2e: {me2}, mask_k2: {mask_k2}]-- B')
md2 = Aeg.decrypt(me2, mask_k2)
print(f'A receives: {md2}')